# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import Optional

from python.mypackage import ListNode


class Solution:
    """
    方法：将链表向右旋转k个位置
        1. 计算链表长度n并找到尾节点
        2. k对n取模得到实际需要旋转的位置
        3. 将尾节点指向头节点形成环形链表
        4. 找到新的头尾节点并断开环形链表

    Args:
        head: Optional[ListNode] - 链表头节点
        k: int - 需要旋转的位置数

    Returns:
        Optional[ListNode] - 旋转后的链表头节点

    Time: O(n) - n为链表长度,需要遍历一次链表
    
    Space: O(1) - 只使用常数额外空间
    """
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if  k == 0 or not head or not head.next:
            return head
        n = 1
        tail = head
        while tail.next:
            tail = tail.next
            n += 1
        k = k % n
        if k == 0:
            return head
        # 形成环形链表
        tail.next = head
        # 找到新的头节点和尾节点
        new_tail = head
        for _ in range(n - k -1):
            new_tail = new_tail.next
        new_head = new_tail.next
        new_tail.next = None
        return new_head


        